package com.mc.algorithm;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
public class LeastK {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o2-o1;
            }
        });
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        int i=0;
        while(i<input.length){
            if(i<k)
            	pq.offer(input[i]);
            else{
                int top = pq.peek();
                if(input[i]<top){
                    pq.poll();
                    pq.offer(input[i]);
                }
            }
            i++;
        }
 		list.addAll(pq);
        return list;
    }
}